//编写一个函数，检查输入的链表是否是回文的。 
//
// 
//
// 示例 1： 
//
// 输入： 1->2
//输出： false 
// 
//
// 示例 2： 
//
// 输入： 1->2->2->1
//输出： true 
// 
//
// 
//
// 进阶： 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？ 
//
// Related Topics 栈 递归 链表 双指针 👍 155 👎 0


package LeetCode.editor.cn;


/**
 * @author ldltd
 * @date 2025-06-17 19:57:42
 * @description 面试题 02.06.回文链表
 
 */
 
public class PalindromeLinkedListLcci {
    public static void main(String[] args) {
    //测试代码
    PalindromeLinkedListLcci fun = new PalindromeLinkedListLcci();
    Solution solution= fun.new Solution();
    
    }

//leetcode submit region begin(Prohibit modification and deletion)

//  Definition for singly-linked list.
  public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

class Solution {
        // 寻找中点+反转链表再比较
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }

        ListNode p1=head;
        ListNode p2=head;
        while (p1!=null&&p1.next!=null){
            p1=p1.next.next;
            p2=p2.next;
        }
        p1=p2;
        ListNode pre=null;
        while (p1!=null){
            ListNode ne=p1.next;
            p1.next=pre;
            pre=p1;
            p1=ne;
        }
        p1=head;
        p2=pre;
        while (p1!=null&&p2!=null){
            if(p1.val!=p2.val) return false;
            p1=p1.next;
            p2=p2.next;
        }
        return true;

    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
